27. 智能驾驶[200分]

题目内容

有一辆汽车需要从 M × N 的地图左上角（起点）开往地图的右下角（终点），去往每一个地区都需要消耗一定的油量，加油站可进行加油。

请你计算汽车确保从起点到达终点时所需的最少初始油量。

说明：

• 智能汽车可以上下左右四个方向移动。
• 地图上的数字取值是 0 或 -1 或正整数：
  • -1：表示加油站，可以加满油，汽车的油箱容量最大为 100；
  • 0：表示这个地区是障碍物，汽车不能通过；
  • 正整数：表示汽车走过这个地区的耗油量。
• 如果汽车无论如何都无法到达终点，则返回 -1。

输入描述

输入共 M + 1 行：

• 第一行：两个数字 M、N，表示地图的大小为 M × N，0 < M, N ≤ 200
• 接下来 M 行：每行 N 个数字，即地图矩阵，其中的值是 0 或 -1 或正整数，数字之间以英文逗号分隔

加油站的总数不超过 200 个。

输出描述

• 如果汽车无论如何都无法到达终点，则返回 -1
• 如果汽车可以到达终点，则返回最少的初始油量

样例

样例 1

输入

2,2
10,20
30,40

输出

70

说明： 行走的路线为：右 → 下。

样例 2

输入

4,4
10,30,30,20
30,30,-1,10
0,20,20,40
10,-1,30,40

输出

70

说明： 行走的路线为：右 → 右 → 下 → 下 → 下 → 右。

样例 3

输入

4,5
10,0,30,-1,10
30,0,20,0,20
10,0,10,0,30
10,-1,30,0,10

输出

60

说明： 行走的路线为：下 → 下 → 下 → 右 → 右 → 上 → 上 → 上 → 右 → 右 → 下 → 下 → 下。

样例 4

输入

4,4
10,30,30,20
30,30,20,10
10,20,10,40
10,20,30,40

输出

-1

说明： 无论如何都无法到达终点。

代码

const readline = require('readline')
const rl = readline.createInterface({
    input: process.stdin,
    output: process.stdout
})
const lines = []
rl.on('line', line => {
    lines.push(line.trim())
})
rl.on('close', () => {
    let idx = 0
    const [m, n] = lines[idx++].split(',').map(Number)
    const grid = []
    for (let i = 0; i < m; i++) {
        grid.push(lines[idx++].split(',').map(Number))
    }

    const dir = [[-1, 0], [1, 0], [0, -1], [0, 1]]

    function check(startFuel) {
        if (startFuel < grid[0][0]) {
            return false
        }

        let initFuel = startFuel - grid[0][0]
        const queue = [[0, 0, initFuel]]

        const best = Array.from({ length: m }, () => new Array(n).fill(-1));
        best[0][0] = initFuel

        while (queue.length) {
            const [x, y, rest] = queue.shift()
            if (x === m - 1 && y === n - 1) {
                return true
            }
            for (let [dx, dy] of dir) {
                const nx = x + dx
                const ny = y + dy

                if (nx >= 0 && nx < m && ny >= 0 && ny < n) {
                    if (grid[nx][ny] === 0) {
                        continue
                    } else if (grid[nx][ny] === -1) {

                        if (100 <= best[nx][ny]) {
                            continue
                        }
                        queue.push([nx, ny, 100])
                        best[nx][ny] = 100
                    } else {
                        const next = rest - grid[nx][ny]
                        if (next <= best[nx][ny]) {
                            continue
                        }
                        queue.push([nx, ny, next])
                        best[nx][ny] = next
                    }
                }
            }
        }
        return false
    }

    if (!check(100)) {
        console.log(-1)
        return
    }
    let left = 1
    let right = 100
    while (left < right) {
        let mid = Math.floor((left + right) / 2)

        if (!check(mid)) {
            left = mid + 1
        } else {
            right = mid
        }
    }
    console.log(left)
});